Voronoi diagrams have been known as one of the central topics in many disciplines in science and engineering, including computational geometry. Due to its natural descriptive and manipulative capabilities, the Voronoi diagram and its variations have been known by names, such as a Thiessen polygon, a medial axis transformation (MAT), a symmetric axis transformation (SAT), a skeleton, a proximity map, a Dirichlit tessellation, a thinning, and a variety of other names.
Ordinary Voronoi diagrams for point sets (also referred to as “point-set Voronoi diagrams”) have been studied extensively, and their properties are well-known to those having skill in the art. Two-dimensional (2D) and higher order analyses have been performed on point-set Voronoi diagrams. These point-set Voronoi diagrams are also referred to herein as VD(P).
One example of a VD(P) is shown in FIG. 1. As shown in FIG. 1, the VD(P) includes a set of points 105a . . . 105c (referred to in the aggregate as 105). Between each pair of points there exists an edge 115a . . . 115c (referred to in the aggregate as 115). Each edge 115 is a perpendicular bisector of a line segment that joins its corresponding points 105. For example, edge 115a is a perpendicular bisector for the line segment that joins points 105a and 105b; edge 115c is the perpendicular bisector for points 105a and 105c; edge 115b is the perpendicular bisector between points 105b and 105c, etc.
As seen in FIG. 1, the VD(P) also has vertices 110a . . . 110c (referred to in the aggregate as 110). These vertices 110 represent a point that is equidistant from three points 105. In that regard, an edge 110 can be seen as disappearing at a vertex 110, or, alternatively, two edges 110 can be seen as coming together to form a vertex 110. As is known, the edges 115 and vertices 110 define polygons 120a . . . 120c (referred to in the aggregate as 120), with each polygon 120 containing its corresponding point 105. In that regard, a polygon 120 is considered the Voronoi region for its corresponding point 105. The network of polygons 120 therefore represents the VD(P).
While not a trivial task, the analysis methods related to VD(P) have been extended in an effort to analyze and characterize Voronoi diagrams of circle sets. Such circle-set Voronoi diagrams are also referred to herein as VD(C).
A more sophisticated approach was developed in which a Euclidean Voronoi diagram of circles was calculated from the circumference of the circles, rather than from the centers of the circles. Such Euclidean Voronoi diagrams for circles are also referred to herein as EVD(C).
One example of a EVD(C) is shown in FIG. 2. As shown in FIG. 2, the EVD(C) includes circles 210 that are defined, in part, by their corresponding centers 205. Rather than simply bisecting the centers of the circles 210, each point on an edge 215 is equidistant from the nearest point on the circumference of its corresponding circles 210. In that regard, each point on the edge 215 has the same Euclidean distance to the nearest point on the circumference of one corresponding circle as it does to the other corresponding circle. The vertices 220 represent the point that has more than two nearest-neighbor circles 210.
For circles of uniform size, the EVD(C) and the VD(P) for the centers of the circles are virtually indistinguishable. However, as shown in FIG. 2, for non-uniform circles 210, the edges 215 of the EVD(C) can be represented by a hyperbolic function. These hyperbolic functions are described in various papers that have been published, in which the topology and geometry of 2D EVD(C) have been analyzed. For example, two articles by Kim et al. have described in detail the computation of EVD(C). Namely, “Voronoi Diagram of a Circle Set from Voronoi Diagram of a Point Set: I. Topology” and “Voronoi Diagram of a Circle Set from Voronoi Diagram of a Point Set: II. Geometry,” published in 2001 in Computer Aided Geometric Design, Volume 18, pages 541-562 and 563-585, respectively. Since the calculation of EVD(C) is known in the art, as evidenced by the publications of Kim et al., further discussion of EVD(C) is omitted here.
Others have attempted to extend the methods of analyzing VD(P) and the EVD(C) to calculate three-dimensional (3D) sphere-set Voronoi diagrams. These sphere-set Voronoi diagrams are also referred to herein as EVD(S). For example, Hans-Martin Will, in his 1999 dissertation (“Computation of Additively-Weighted Voronoi Cells for Applications in Molecular Biology,” Swiss Federal Institute of Technology, Zurich), explained the mathematics behind EVD(S) in great detail. In his dissertation, Will refers to the EVD(S) as additively-weighted Voronoi cells (AWVC). In addition to providing the detailed mathematics behind his model, Will provided an example algorithm for implementing the computation of AWVC for a single Voronoi region.
In a 1999-paper by Luchnikov et al. (“Voronoi-Delaunay Analysis of Voids in Systems of Nonspherical Particles,” Physical Review E, Volume 59, Number 6, June 1999), computations of a single Voronoi region for various 3D models were presented. However, in that approach, Luchnikov presented the idea of using a numerical approach, which is relatively cumbersome and inefficient.
Thus, despite such skill in the art, there is still a lack of appropriate algorithms and stable running codes that can calculate a complete Euclidean Voronoi diagram in 3D. Thus, due to the complexities and intricacies of computing a complete Euclidean Voronoi diagram in 3D, many have instead implemented ordinary VD(P), power diagrams, or alpha-shape algorithms, which are known in the art. A need therefore exists in the art for a more practical solution.